package com.hyper_yang.algorithmRecord;

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;

// 239. 滑动窗口最大值
public class LeetCode_239 {
    /*
        给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
        你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
        返回 滑动窗口中的最大值 。
     */
    // 方法一: 暴力法 O(n * k)
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        // 定义结果数组
        int[] res = new int[nums.length - k + 1];
        // 遍历数组
        for (int i = 0; i <= nums.length - k; i++) {
            int max = nums[i];
            for (int j = 0; j < k; j++) {
                if (nums[i + j] > max) max = nums[i + j];
            }
            res[i] = max;
        }
        return res;
    }

    // 方法二: 大顶堆 O(n * log(k))
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        // 定义结果数组
        int[] res = new int[nums.length - k + 1];
        // 用优先队列实现一个大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        // 构建大顶堆
        for (int i = 0; i < k; i++)
            maxHeap.add(nums[i]);
        res[0] = maxHeap.peek();
        // 遍历数组
        for (int i = 1; i <= nums.length - k; i++) {
            maxHeap.remove(nums[i - 1]);
            maxHeap.add(nums[i + k - 1]);
            res[i] = maxHeap.peek();
        }
        return res;
    }

    // 方法三: 双向队列 O(n)
    public static int[] maxSlidingWindow3(int[] nums, int k) {
        // 定义结果数组
        int[] res = new int[nums.length - k + 1];
        // 双向队列
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        // 初始化
        for (int i = 0; i < k; i++) {
            // 如果队尾元素小于当前元素，直接删除
            while (!deque.isEmpty() && nums[i] > nums[deque.getLast()])
                deque.removeLast();
            deque.addLast(i);
        }
        res[0] = nums[deque.getFirst()];
        // 遍历数组
        for (int i = k; i < nums.length; i++) {
            // 删除的元素是否是之前的最大值
            if (!deque.isEmpty() && deque.getFirst() == i - k)
                deque.removeFirst();

            while (!deque.isEmpty() && nums[i] > nums[deque.getLast()])
                deque.removeLast();
            deque.addLast(i);

            res[i - k + 1] = nums[deque.getFirst()];
        }
        return res;
    }

    // 方法四: 左右扫描 O(n)
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 定义结果数组
        int[] res = new int[nums.length - k + 1];
        // 定义存放块内最大值的 left和 right数组
        int[] left = new int[n];
        int[] right = new int[n];
        // 遍历数组，左右扫描
        for (int i = 0; i < n; i++) {
            // 从左到右:
            if (i % k == 0) left[i] = nums[i];  // 块起始位置
            else left[i] = Math.max(left[i - 1], nums[i]); // 不是起始位置，和上个元素比较

            // 从右到左:
            int j = n - 1 - i;
            if (j % k == k - 1 || j == n - 1) right[j] = nums[j];
            else right[j] = Math.max(right[j + 1], nums[j]);
        }
        // 对每个窗口计算最大值
        for (int i = 0; i < n - k + 1; i++) {
            res[i] = Math.max(right[i], left[i + k - 1]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        for (int i : res) {
            System.out.print(i + "\t");
        }
    }
}
